import collections
from typing import List


class Trie:
    class _Node:
        def __init__(self):
            self.value = None
            self.count = 0
            self.children = {}

        def __contains__(self, ch):
            return ch in self.children

        def __getitem__(self, ch):
            return self.children[ch]

    def __init__(self):
        self.root = self._Node()

    def add(self, word):
        """向字典树中添加词语"""
        node = self.root
        for ch in word:
            if ch not in node:
                node.children[ch] = self._Node()
            node.count += 1
            node = node.children[ch]
        node.value = word

    def __contains__(self, word):
        """判断词语是否存在"""
        node = self.root
        for ch in word:
            if ch not in node:
                return False
            node = node.children[ch]
        return node.value == word

    def search(self, string):
        """寻找字符串中从头开始的第1个词语（如果没有找到则返回None）"""
        node = self.root
        for ch in string:
            if ch not in node:
                return None
            node = node.children[ch]
            if node.value is not None:
                return node.value


class StreamChecker:

    def __init__(self, words: List[str]):
        self.trie = Trie()
        for word in words:
            self.trie.add(word[::-1])
        self.last = collections.deque()

    def query(self, letter: str) -> bool:
        self.last.appendleft(letter)
        return self.trie.search(self.last) is not None


if __name__ == "__main__":
    obj = StreamChecker(["cd", "f", "kl"])
    print(obj.query("a"))  # False
    print(obj.query("b"))  # False
    print(obj.query("c"))  # False
    print(obj.query("d"))  # True
    print(obj.query("e"))  # False
    print(obj.query("f"))  # True
    print(obj.query("g"))  # False
    print(obj.query("h"))  # False
    print(obj.query("i"))  # False
    print(obj.query("j"))  # False
    print(obj.query("k"))  # False
    print(obj.query("l"))  # True
